﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace ConsoleApplication27
{
    public class RabinMiller
    {

        public List<Liczba> primes = new List<Liczba>();


        public  void test(Liczba n, Random r)
        {
            Console.WriteLine("TEST {0}",n);
            Liczba jeden = new Liczba("1", n.system);
            if (Pomoce.Porownaj(n, jeden) != 2)
            {
               
                Liczba dwa = new Liczba("2", n.system);
                

                Liczba t = n - jeden;

                Liczba pminus1 = t;
                Liczba pminusdwa = pminus1 - jeden;
                int s = 0;



                while ((t % dwa).element[0] == 0)
                {
                    t = t / dwa;
                    s++;
                   

                }
                bool czypierwsza = false;


                for (int i = 0; i < 25; i++)
                {
                    Liczba a = Pomoce.random(pminusdwa,r);


                    Liczba x = PotegowanieModulo.modulo(a, t, n);
                    if (Pomoce.Porownaj(x, jeden) == 2 || Pomoce.Porownaj(x, pminus1) == 2)
                    {
                        czypierwsza = true;
                    }
                    else
                    {


                        int j = 1;
                        while (j < s)
                        {
                            x = x * x;
                            x = x % n;
                            if (Pomoce.Porownaj(x, jeden) == 2) { i = 50; czypierwsza = false; break; }
                            if (Pomoce.Porownaj(x, pminus1) == 2) { czypierwsza = true; break; }
                            j++;
                        }
                        if (czypierwsza != true) i = 50;



                    }
                }
                if (czypierwsza == true) { Console.WriteLine(n); primes.Add(n); }
               
            }

           

        }






    }
}
